//
// Created by Jisam on 12/09/2024 5:40 PM.
// Solution of  P3953 [NOIP2017 提高组] 逛公园
//#pragma GCC optimize(3)
#include <bits/stdc++.h>

using namespace std;
#define coutn(x) cout << (x) << "\n"
#define endl "\n"
#define PSI pair<string,int>
#define PII pair<int,int>
#define PDI pair<double,int>
#define PDD pair<double,double>
#define VVI vector<vector<int>>
#define VI vector<int>
#define VS vector<string>
#define PQLI priority_queue<int, vector<int>, less<int>>
#define PQGI priority_queue<int, vector<int>, greater<int>>
#define code_by_jisam ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
typedef long long i64;
typedef unsigned u32;
typedef unsigned long long u64;
typedef __int128 i128;
int dx[] = {-1, 1, 0, 0, 1, 1, -1, -1,};
int dy[] = {0, 0, -1, 1, 1, -1, -1, 1,};

// 定义最大节点数常量
const int MAXN = 1e5 + 5;
// 定义长整型变量前缀
i64 t, d[MAXN], f[MAXN][55], n, m, k, p;
// 定义访问标记数组
bool vis[MAXN][55];
// 定义图中的节点结构
struct node {
    i64 to, edge;
};

// 定义邻接表存储图结构
vector<node> head[MAXN], h[MAXN];

/**
 * 动态规划函数，计算从根节点到叶子节点的所有路径中，路径长度为l的方案数
 * @param root 当前处理的节点
 * @param l 当前路径的长度
 * @return 路径长度为l的方案数
 */
int dfs(int root,int l)
{
    // 检查路径长度是否合法
    if(l < 0 || l > k) return 0;
    // 如果该节点和路径长度已被访问过，返回-1表示不可达
    if(vis[root][l]) {
        vis[root][l] = false;
        return -1;
    }
    // 如果该节点和路径长度已记录过结果，直接返回结果
    if(f[root][l] != -1)
    {
        return f[root][l];
    }
    // 标记当前节点和路径长度已访问
    vis[root][l] = true;
    int ans = 0;
    // 遍历当前节点的所有邻接节点
    for(int i = 0; i < h[root].size() ; i ++)
    {
        node e = h[root][i];
        // 递归计算子节点的方案数
        int val = dfs(e.to,d[root] + l - d[e.to] - e.edge);
        // 如果子节点不可达，则当前节点也不可达
        if(val == -1)
        {
            vis[root][l] = false;
            return -1;
        }
        // 累加子节点的方案数
        ans = (ans + val) % p;
    }
    // 取消标记
    vis[root][l] = false;
    // 特殊处理根节点和路径长度为0的情况
    if(root == 1 && l == 0)
    {
        ans ++;
    }
    // 记录结果
    f[root][l] = ans;
    return ans;
}

/**
 * 解决方案函数
 */
void solution() {
    // 输入节点数、边数、路径最大长度和模数
    cin >> n >> m >> k >> p;
    // 清空图结构
    for (int i = 1; i <= n; i++) {
        head[i].clear();
        h[i].clear();
    }
    // 输入边的信息
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        node e;
        e.to = b;
        e.edge = c;
        head[a].push_back(e);
        e.to = a;
        h[b].push_back(e);
    }
    // 初始化最短路径数组
    memset(d,0x3f3f3f,sizeof d);
    memset(f,-1 ,sizeof f);
    // 广度优先搜索计算最短路径
    queue<int> q;
    q.push(1);
    d[1] = 0;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < head[x].size(); i ++)
        {
            if(d[head[x][i].to] > d[x] + head[x][i].edge){
                d[head[x][i].to] = d[x] + head[x][i].edge;
                q.push(head[x][i].to);
            }
        }
    }
    // 初始化答案变量
    int ans = 0;
    // 遍历所有可能的路径长度，累加方案数
    for(int i = 0 ; i <= k ; i ++)
    {
        int val = dfs(n,i);
        if(val == -1) {
            coutn(val);
            return;
        }
        ans = (ans + val) % p;
    }
    // 输出最终答案
    coutn(ans);
    return;
}

int main() {
    code_by_jisam;
    i64 T = 1;
    cin >> T;
    while (T--) {
        solution();
    }
    return 0;
}